package Algorithm.string;

import java.util.Arrays;

/**
 * @Desc:   字符串的排列
 *          给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 *          换句话说，第一个字符串的排列之一是第二个字符串的子串。
 *          输入: s1 = "ab" s2 = "eidbaooo"
 *          输出: True
 *          解释: s2 包含 s1 的排列之一 ("ba").
 *
 *          示例2:
 *          输入: s1= "ab" s2 = "eidboaoo"
 *          输出: False
 *
 *          true
 *          "abc"
 *          "bbbca"
 *
 *          false
 *           "hello"
 *           "ooolleoooleh"
 *
 * @author: cww
 * @DateTime: 2020/3/30 9:21
 */

public class CheckInclusion {
    static boolean  flag = false;
    public static boolean checkInclusion(String s1, String s2) {
        permute(s1, s2, 0);
        return flag;
    }
    public static String swap(String s, int i0, int i1) {
        if (i0 == i1)
            return s;
        String s1 = s.substring(0, i0);
        String s2 = s.substring(i0 + 1, i1);
        String s3 = s.substring(i1 + 1);
        return s1 + s.charAt(i1) + s2 + s.charAt(i0) + s3;
    }
    static void  permute(String s1, String s2, int l) {
        if (l == s1.length()) {
            if (s2.indexOf(s1) >= 0)
                flag = true;
        } else {
            for (int i = l; i < s1.length(); i++) {
                s1 = swap(s1, l, i);
                permute(s1, s2, l + 1);
                s1 = swap(s1, l, i);
            }
        }
    }



    public static void main(String[] args) {
        String s1 = "abc";
        String s2 = "dcda";
        System.out.println(checkInclusion2(s1, s2));
    }


    /**
     * 排序法，将s1进行排序，将 s2要匹配的区间也排序，再用排序后的 s1 与 s2 比对
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion1(String s1, String s2) {
        String s = sort(s1);
        for(int i =0; i<=s2.length()-s1.length();i++){
            if(s.equals(sort(s2.substring(i, i+s.length())))) return true;
        }
        return false;
    }

    public static String sort(String s) {
        char[] c = s.toCharArray();
        Arrays.sort(c);
        return new String(c);
    }

    /**
     * 我们可以使用更简单的数组数据结构来存储频率，而不是仅使用特殊的哈希表数据
     * 结构来存储字符出现的频率。给定字符串仅包含小写字母（'a'到'z'）。因此我
     * 们需要采用大小为 26 的数组。其余过程与最后一种方法保持一致。
     *
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion2(String s1, String s2) {
        if(s1.length() > s2.length()) return false;
        int[] s1Array = new int[26];
        for(int i=0;i<s1.length();i++){
            s1Array[s1.charAt(i)-'a']++;
        }
        for(int i=0;i<=s2.length()-s1.length();i++){
            int[] s2Array = new int[26];
            for(int j=0;j<s1.length();j++){
                s2Array[s2.charAt(i+j)-'a']++;
            }
            if(compare(s1Array,s2Array)) return true;
        }
        return false;
    }

    public static boolean compare(int[] int1, int[] int2){
        for(int i=0;i<26;i++){
            if(int1[i]!=int2[i]){
                return false;
            }
        }
        return true;
    }

    public static boolean checkInclusion2_1(String s1, String s2){
        if(s1.length()>s2.length()) return false;
        int[] s1Array = new int[26];
        for(int i=0;i<s1.length();i++){
            s1Array[s1.charAt(i)-'a']++;
        }
        for(int j=0;j<=s2.length()-s1.length();j++){
            int[] s2Array = new int[26];
            for(int i=0;i<j+s1.length();j++){
                s2Array[s2.charAt(i) - 'a']++;
            }
            if(compare1(s1Array, s2Array)) return true;
        }
        return false;
    }

    public static boolean compare1(int[] int1,int[] int2){
        for(int i=0;i<26;i++){
            if(int1[i] != int2[i]) return false;
        }
        return true;
    }
}
